package com.testjava.julycode;


/**
 * 1.1 旋转字符串
 * (github链接：https://github.com/julycoding/The-Art-Of-Programming-By-July/blob/master/ebook/zh/01.01.md)
 *
 * Created by lingguo on 14-6-26.
 */
public class RotateString {
    /**
     * 问题描述：
     *  给定一个字符串，要求把字符串前面的若干个字符移动到字符串的尾部，如把字符串“abcdef”前面的2个字符'a'和'b'移动到字符串
     *  的尾部，使得原字符串变成字符串“cdefab”。请写一个函数完成此功能，要求对长度为n的字符串操作的时间复杂度为 O(n)，空间
     *  复杂度为 O(1)。
     *
     * 思路：
     *  三步旋转法：(X^TY^T)^T=YX
     *
     * @param str   输入串
     * @param n     前n个字符移到串的最后
     * @return      翻转后的串
     */
    public static char[] leftRotateString(char[] str, int n) {
        char[] rotateLeft = rotate(str, 0, n - 1);
        char[] rotateRight = rotate(rotateLeft, n, str.length - 1);
        char[] result = rotate(rotateRight, 0, str.length - 1);
        return result;
    }

    public static void main(String[] args){
        String t = "abcdef";

        char[] res = RotateString.leftRotateString(t.toCharArray(), 3);

        System.out.println(res);
    }

    public static char[] rotate(char[] str, int from, int to){
        char tmp;
        while (from < to){
            tmp = str[from];
            str[from] = str[to];
            from++;
            str[to] = tmp;
            to--;
        }
        return str;
    }
}
